package pers.qianyu.month_202101.date_20210114;

/**
 * 706. 设计哈希映射
 * https://leetcode-cn.com/problems/design-hashmap/
 * - 拉链法实现（数组 + 链表实现）
 *
 * @author mizzle rain
 * @date 2021年1月14日17:28:48
 */
public class MyHashMap {
    private static final int N = 20011;
    private Node[] table;

    private static class Node {
        int key, value;
        Node next;

        public Node(int key, int value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    /**
     * Initialize your data structure here.
     */
    public MyHashMap() {
        table = new Node[N];
    }

    /**
     * value will always be non-negative.
     */
    public void put(int key, int value) {
        int hash = hash(key);
        Node node = table[hash];
        if (node == null) {
            table[hash] = new Node(key, value, null);
        } else {
            Node p = node, pre = null;
            while (p != null) {
                if (p.key == key) {
                    p.value = value;
                    return;
                }
                pre = p;
                p = p.next;
            }
            pre.next = new Node(key, value, null);
        }
    }

    /**
     * Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
     */
    public int get(int key) {
        int hash = hash(key);
        Node node = table[hash];
        if (node != null) {
            Node p = node;
            while (p != null) {
                if (p.key == key) {
                    return p.value;
                }
                p = p.next;
            }
        }
        return -1;
    }

    /**
     * Removes the mapping of the specified value key if this map contains a mapping for the key
     */
    public void remove(int key) {
        int hash = hash(key);
        Node node = table[hash];
        if (node == null) {
            return;
        }
        Node p = node;
        if (node.key == key) {
            Node temp = node.next;
            node.next = null;
            table[hash] = temp;
            return;
        }
        Node pre = null;
        while (p != null) {
            if (p.key == key) {
                pre.next = p.next;
                p.next = null;
            }
            pre = p;
            p = p.next;
        }
    }

    private int hash(int key) {
        return key % N;
    }

    public static void main(String[] args) {
        MyHashMap map = new MyHashMap();
    }
}

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap obj = new MyHashMap();
 * obj.put(key,value);
 * int param_2 = obj.get(key);
 * obj.remove(key);
 */